// 子集2

package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class solution_090 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // int[0]存储数字,int[1]存储该数字的数量
        List<int[]> count = new ArrayList<>();
        Arrays.sort(nums);
        // count.add(new int[] { nums[0], 1 });
        for (int i = 0; i < nums.length; i++) {
            if (!count.isEmpty() && count.get(count.size() - 1)[0] == nums[i])
                count.get(count.size() - 1)[1]++;
            else
                count.add(new int[] { nums[i], 1 });
        }
        BackTrace(result, count, 0, new ArrayList<>());
        // for (int[] i : count)
        // System.out.println(i[0] + "@" + i[1]);
        // System.out.println(result);
        return result;
    }

    public void BackTrace(List<List<Integer>> result, List<int[]> count, int currentLen, List<Integer> combiantion) {
        if (currentLen == count.size()) {
            result.add(new ArrayList<>(combiantion));
            return;
        } else if (currentLen > count.size())
            return;
        else {
            // 不加该元素
            BackTrace(result, count, currentLen + 1, combiantion);
            // 加n个该元素
            for (int i = 0; i < count.get(currentLen)[1]; i++) {
                combiantion.add(count.get(currentLen)[0]);
                BackTrace(result, count, currentLen + 1, combiantion);
            }
            // 删除刚才添加的元素用于回溯
            for (int i = 0; i < count.get(currentLen)[1]; i++) {
                combiantion.remove(combiantion.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        solution_090 s = new solution_090();
        int[] nums = new int[] { 3, 3, 2 };
        s.subsetsWithDup(nums);
    }
}

public class Solution090 {

}
